A. Field of the Invention
The present invention relates generally to data switching and routing, and more particularly, to systems and methods for controlling data flow.
B. Description of Related Art
Routers receive data on physical media, such as optical fiber, analyze the data to determine its destination, and output the data on physical media in accordance with the destination. Routers were initially designed using a general purpose processor executing large software programs. As line rates and traffic volume increased, however, general purpose processors could not scale to meet these new demands. For example, as functionality was added to the software, such as accounting and policing functionality, these routers suffered performance degradation. In some instances, the routers failed to handle traffic at line rate when the new functionality was turned on.
To meet the new demands, purpose-built routers were architected. Purpose-built routers are designed and built with components optimized for routing. They not only handled higher line rates and higher network traffic volume, they also added functionality without compromising line rate performance.
Flow-control refers to the metering of packet flow through the network and/or through the router. For example, it may be desirable to limit the number of packets received from a certain port of the router to a pre-designated rate. One known method of implementing flow-control is based on a credit system. With this method, each data flow that is to be controlled is associated with a credit counter. As packets in the flow are transmitted by the router, the credit counter is decremented. Conversely, the credit counter is incremented based on a credit replenishment scheme, such as by periodically incrementing the credit counter up to a maximum credit amount. The router checks the credit counter before transmitting a packet and drops the packet if the credit counter is below a predetermined value. Through the operation of this type of credit-counter, the router can enforce a data flow policy such as limiting the maximum transmission rate for a particular data flow below a certain rate.
FIG. 1 is a diagram illustrating an exemplary situation in which flow control may be used to enforce data flow policies. As is generally shown in FIG. 1, an Internet Service Provider (ISP) 104 may provide network services to a number of customers. A customer may be, for example, a corporation or an individual. Each customer is associated with a customer router/switch 101-103. Routers/switches 101-103 connect the users associated with a customer, such as users 110, to ISP 104. ISP 104, in turn, connects the customers to network 105 (e.g., the Internet). Routers 120 of ISP 104 handle the actual routing of packet data between network 105 and the customer routers/switches 101-103.
ISP 104 may wish to give each customer a predetermined guaranteed bandwidth. The total bandwidth of the data flow coming from each customer should not exceed this bandwidth. If it does, ISP 104 may drop packets from the customer's data flow. Traditional credit-based flow control techniques, such as those discussed above, may be used by ISP 104 to manage the bandwidth being used by the ISP's customers.
One drawback of traditional credit-based flow control techniques is that these techniques tend to produce “choppy” traffic patterns when interacting with other network protocols, such as the commonly used Transmission Control Protocol (TCP). FIG. 2 is a diagram illustrating a typical choppy traffic pattern that occurs through the interaction of TCP with traditional credit-based traffic flow techniques. Line 201 represents the predetermined maximum bandwidth available to the customer. Line 202 represents the instantaneous bandwidth of a packet flow. Above line 201, conventional credit-based flow control techniques drop all packets. The sudden increase in dropped packets may cause network devices that implement TCP earlier in the data flow path to respond by scaling back the rate of transmitted packets, causing the transmitted bandwidth to suddenly decrease. This pattern of over-transmission followed by over-reduction in the bandwidth of the data flow forms the choppy data flow pattern shown by line 202. This type of pattern flow makes inefficient use of the allotted bandwidth.
Accordingly, there is a need in the art to improve traditional flow control techniques.